#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int max = 0;
//        for (int left = 0, right = height.size() - 1; left < right; )
//        {
//            int sum = (right - left) * (height[left] > height[right] ? height[right--] : height[left++]);
//            if (sum > max)
//                max = sum;
//        }
//
//        return max;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        for (int i = 0; i < nums.size() - 2;)
//        {
//            int target = -1 * nums[i];
//            for (int left = i + 1, right = nums.size() - 1; left < right;)
//            {
//                if (nums[left] + nums[right] == target)
//                {
//                    vector<int> arr = { nums[i], nums[left], nums[right] };
//                    ret.push_back(arr);
//                    while (--right > left && nums[right] == nums[right + 1]);
//                    while (++left < right && nums[left] == nums[left - 1]);
//
//                }
//                else if (nums[left] + nums[right] > target)
//                {
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//            while (++i < nums.size() - 2 && nums[i] == nums[i - 1]);
//        }
//
//        return ret;
//    }
//};

//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ret = 0;
//        for (int i = 0; i < height.size() - 1;)
//        {
//            int l = i, r = i;
//            while (r + 1 < height.size() && (height[r + 1] < height[l] && height[r] > height[r + 1])) r++;
//            while (r + 1 < height.size() && height[r] < height[r + 1])
//            {
//                r++;
//                if (height[r] > height[l]) break;
//            }
//
//            if (r < height.size())
//            {
//                int max = height[r] > height[l] ? height[l] : height[r];
//                for (int j = l + 1; j < r; j++)
//                {
//                    ret += max - height[j];
//                }
//
//                i = r;
//            }
//            else i++;
//        }
//
//        return ret;
//    }
//};
//
//
//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ret = 0;
//        for (int i = 0; i < height.size() - 1;)
//        {
//            int l = i, r = i;
//            while (r + 1 < height.size() && (height[r + 1] < height[l] && height[r + 1] < height[r])) r++;
//            int max = height[r];
//            for (int j = r; j < height.size() && height[j] < height[l]; )
//            {
//                if (j + 1 < height.size() && height[j + 1] >= height[j])
//                {
//                    j++;
//                }
//                else if (j + 1 < height.size() && height[j + 1] < height[j])
//                {
//                    if (height[j] > max)
//                    {
//                        max = height[j];
//                        r = j;
//                    }
//                    else break;
//                }
//            }
//        }
//
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ret = 0;
//        int max = height[0];
//        for (int i = 1; i < height.size(); i++)
//        {
//            if (height[i] > max) max = height[i];
//        }
//
//        for (int i = 1; i <= max; i++)
//        {
//            for (int j = 1; j < height.size() - 1; j++)
//            {
//                if (height[j] < i)
//                {
//                    int l = j - 1, r = j + 1;
//                    while (l >= 0 && r < height.size())
//                    {
//                        if (height[l] < i)
//                        {
//                            l--;
//                            continue;
//                        }
//                        if (height[r] < i)
//                        {
//                            r++;
//                            continue;
//                        }
//                        if (height[l] >= i && height[r] >= i)
//                        {
//                            ret += r - l - 1;
//                            for (int k = l + 1; k < r; k++)
//                            {
//                                height[k] += 1;
//                            }
//                            break;
//                        }
//                    }
//                }
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//
//    int _trap(vector<int>& h, int begin, int end)
//    {
//        if (end - begin < 3) return 0;
//
//
//        int index = 0;
//        for (int i = begin  + 1; i <= end - 1; i++)
//        {
//            if (h[index] < h[i])
//            {
//                index = i;
//            }
//        }
//
//        if (index < begin || index < end)
//        {
//            int sum = 0;
//            int min = h[begin] > h[end] ? h[end] : h[begin];
//            for (int i = begin + 1; i < end; i++)
//            {
//                sum += min - h[i];
//            }
//            return sum;
//        }
//        else return _trap(h, begin, index) + _trap(h, index, end);
//    }
//
//    int trap(vector<int>& height)
//    {
//        return _trap(height, 0, height.size() - 1);
//    }
//};

class Solution {
public:
    int trap(vector<int>& height) {
        int ret = 0;
        vector<int> leftMax(height.size());
        leftMax[0] = height[0];
        for (int i = 1; i < height.size(); i++)
        {
            leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];
        }

        vector<int> rightMax(height.size());
        rightMax[height.size() - 1] = height[height.size() - 1];
        for (int i = height.size() - 2; i >= 0; i--)
        {
            rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];
        }

        int leftMax = height[0];

        for (int i = 0; i < height.size(); i++)
        {
            ret += (rightMax[i] > leftMax[i] ? leftMax[i] : rightMax[i]) - height[i];
        }

        return ret;
    }
};

int main()
{
    vector<int> arr = { 0,1,0,2,1,0,1,3,2,1,2,1 };
    Solution().trap(arr);
	return 0;
}